
/*
 * Node.java
 *
 * Created on July 27, 2006, 3:28 PM
 *
 */
package galronnlp.perceptron;

//~--- non-JDK imports --------------------------------------------------------

import galronnlp.cfg.grammar.NaryRule;
import galronnlp.cfg.grammar.Rule;
import galronnlp.util.Scorable;
import galronnlp.util.Symbol;
import galronnlp.util.SymbolGenerator;
import java.util.HashSet;

//~--- JDK imports ------------------------------------------------------------

import java.util.Iterator;
import java.util.LinkedList;

//~--- classes ----------------------------------------------------------------

/**
 *
 * @author Daniel A. Galron
 */
public class Node implements Scorable, Comparable {

    boolean VERBOSE = false;
    boolean STRUCTURE = false;
    
    public static int TERMINAL    = 0;
    public static int POS         = 2;
    public static int NONTERMINAL = 1;

    //~--- fields -------------------------------------------------------------

    // pointer to the parent node
    private Node            parent          = null;
    
    public int              level           = 0;
    
    private Integer         rightDepth      = null;
    
    // pointer to the feature vector for this node
    private FeatureVector   nodeFeatures    = new FeatureVector();
    
    // pointer to the lexical head of the node
    private Node            lexicalHead     = null;
    
    // pointer to the node immediately to the left of this node
    private Node            leftSibling     = null;
    
    // the linked list containing all the children of this node
    public LinkedList<Node> children        = new LinkedList<Node>();
    
    // pointer to the C-Commanding node
    private Node            CCommandingNode = null;
    
    // feature vector with the features of this node, all of its children,
    // etc. It is the sum of the feature vector for this node and all the
    // features of all its descendents
    public FeatureVector    subtreeFeatures = new FeatureVector();
    
    // symbol generator
    private SymbolGenerator gen;
    
    // the look ahead token
    private Symbol          lookAhead;
    
    // the look ahead POS
    private Symbol          lookAheadPOS;
    
    // a pointer to the feature vector containing the parameters, as estimated
    // by the perceptron algorithm
    public FeatureVector   parameters;
    
    // The type of the node (TERMINAL, NONTERMINAL, POS)
    public int              type;
    
    // the symbol value of this node (e.g., NP, S, VP, etc.)
    public Symbol           value;

    
    private LinkedList<String> sentence = null;
    //~--- constructors -------------------------------------------------------

    public Node(Node n) {
        this.type = n.type;
        this.value = n.value;
    }

    /** Creates a new instance of Node */
    public Node(Node p, int t, Symbol v, Symbol lk, Symbol lkp,
                SymbolGenerator g, FeatureVector par) {
        this.lookAhead    = lk;
        this.lookAheadPOS = lkp;
        this.value        = v;
        this.type         = t;
        parent            = p;
        this.gen          = g;
        this.parameters   = par;
    }

    //~--- methods ------------------------------------------------------------

    /**
     
     */
    public int rightDepth() {
        if(rightDepth == null) {
            int count = 0;
            Node nPointer = this;
            while(nPointer.type != Node.TERMINAL) {
                count += 1;
                nPointer = nPointer.children.getLast();
            }
            rightDepth = new Integer(count + 1);
        }
        return rightDepth.intValue();
    }
    
    /**
     * Adds all the chains, allowable triples, and productions which can be derived
     * from this tree to the grammar.
     *
     * @param g The grammar to which to add the chains, allowable triples, and production rules
     * @return the left-most chain of the tree.
     */
    public Chain addToGrammar(Grammar g) {
        LinkedList<Symbol> children = new LinkedList<Symbol>();
        // Add the label of each node to the children LinkedList, and add this node
        // and each adjacent pair of children to the set of allowable Triples
        for(int i = 0; i < this.children.size() - 1; i++) {
            children.addLast(this.children.get(i).label());
            g.addAllowableTriple(this.label(), this.children.get(i).label(), this.children.get(i+1).label());
        }
        children.addLast(this.children.getLast().label());
        // Create a new NaryRule for this node and its children, and add it to
        // the list of productions in the grammar
        Rule r = new NaryRule(this.label(), children);
        g.addProduction(r);
    
        // Get all chains in the tree rooted by this node, and add them to the 
        // grammar
        LinkedList<Chain> chains = new LinkedList<Chain>();
        // If this is a non-terminal node:
        if(this.type == NONTERMINAL) {
            // create a new chain headed by the label of this node
            Chain c = new Chain(this.label());
            // get the left-most chain of this subtree and append it to the chain
            c.append(this.children.getFirst().addToGrammar(g));
            // Add this chain to the list of chains to add to the grammar
            chains.addLast(c.copy());
            // Get the left most chains for all the children of this node. Note
            // that due to recursion, all of the chains in the tree will be added
            // to the grammar.
            for(int i = 1; i < this.children.size(); i++) {
                Chain chain = this.children.get(i).addToGrammar(g);
                chains.addLast(chain);
            }
            g.addChains(chains);
            return c;
        // BASE CASE
        } else if(this.type == POS) {
            // Create a chain consisting of this node and its terminal child.
            Chain c = new Chain(this.label());
            c.append(this.children.getFirst().label());
            chains.addLast(c.copy());
            return c;
        }
        else {
            System.err.println("ERROR! I SHOULDN'T BE HERE: NODE.ADDTOGRAMMAR() " + this.type);
            System.err.println(this);
            return null;
        }
    }
    
    /**
     * Adds a child node or subtree as the right-most child to this node.
     *
     * @param child the node that is the root of the subtree to add to this tree.
     */
    public void addChild(Node child) {
        // If the child does not have a parent node defined, then set this
        // node as its parent node.
        if(child.parent == null) {
            child.parent = this;
        }
        // If this is the first child being added, then simply add it
        if (children.size() == 0) {
            children.addLast(child);
        // Otherwise, if there is a left sibling, set the left sibling pointer in the node to
        // be added to the current right-most child; then add the new node;
        } else {
            child.leftSibling = children.getLast();
            children.addLast(child);
        }
        // Find and set the pointer to the c-commanding node of the new node.
        child.CCommandingNode = child.getCCommandingNode();
        // Set the level of the child as one below the level of this node.
        child.level = this.level + 1;
    }

    
    /**
     * Recursively determines whether the tree rooted by this node is equal to the tree rooted
     * at another node. To do this, we compare only the label of each node and
     * the number of children each node has.
     *
     * @return true if the two trees are equal, false otherwise
     */
    public boolean equals(Object o) {
        Node n = (Node) o;
        // Test to see if the root of the tree (i.e. this) is equal to the root
        // of the other tree, and test to see that they have the same number of
        // childern
        if (this.value.equals(n.value)
                && (this.getChildren().size() == n.getChildren().size())) {
            boolean ret = true;
            // Iterate through all the children, and compare the subtrees rooted
            // at each child
            for (int i = 0; i < this.getChildren().size(); i++) {
                ret &= this.children.get(i).equals(n.getChildren().get(i));
            }
            return ret;
        }

        return false;
    }

    /**
     * This method fires the local features, and builds the global features as 
     * described in the Collins & Roark 2004 paper "" and Collins' 2002 paper ""
     *
     * @param rules The head finder rules to use
     */
    public void fireFeatures(HeadFinderRules rules) {
        this.subtreeFeatures = new FeatureVector();
        this.nodeFeatures = new FeatureVector();
        // If the lexical heads have not yet been percolated, percolate them so
        // that each node in the tree will have a pointer to the lexical head of
        // its constituent.
        if (lexicalHead == null) {
            this.percolateLexicalHeads(rules);
        }
        // Fire the features of each subtree, and then add their global features
        // to the global feature vector of the subtree headed by this node
        for (Iterator<Node> it = children.iterator(); it.hasNext(); ) {
            Node subtree = it.next();
            subtree.fireFeatures(rules);
            this.subtreeFeatures =
                this.subtreeFeatures.add(subtree.subtreeFeatures);
        }
        // Fire the local features at this node if the node is a non-terminal
        // (Fires the features specified in the Collins' & Roark paper)
        if (this.type == NONTERMINAL || this.type == POS) {
            nodeFeatures.fire(new Feature(Feature.L00, this.getLabel(0, 0)));
            nodeFeatures.fire(new Feature(Feature.L10, this.getLabel(1, 0)));
            nodeFeatures.fire(new Feature(Feature.LKP, this.lookAheadPOS));
            nodeFeatures.fire(new Feature(Feature.L01, this.getLabel(0, 1)));
            nodeFeatures.fire(new Feature(Feature.L02, this.getLabel(0, 2)));
            nodeFeatures.fire(new Feature(Feature.L03, this.getLabel(0, 3)));
            nodeFeatures.fire(new Feature(Feature.L20, this.getLabel(2, 0)));
            nodeFeatures.fire(new Feature(Feature.L11, this.getLabel(1, 1)));
            nodeFeatures.fire(new Feature(Feature.L30, this.getLabel(3, 0)));
            nodeFeatures.fire(new Feature(Feature.L21, this.getLabel(2, 1)));
            nodeFeatures.fire(new Feature(Feature.CL, lexicalHead.label()));
            nodeFeatures.fire(new Feature(Feature.LK, this.lookAhead));
            this.subtreeFeatures = this.subtreeFeatures.add(this.nodeFeatures);
        // Fire the local features at this node if the node is a terminal node
        } else {
            nodeFeatures.fire(new Feature(Feature.L00, this.getLabel(0, 0)));
            nodeFeatures.fire(new Feature(Feature.L10, this.getLabel(1, 0)));
            nodeFeatures.fire(new Feature(Feature.L20, this.getLabel(2, 0)));
            nodeFeatures.fire(new Feature(Feature.L11, this.getLabel(1, 1)));
            nodeFeatures.fire(new Feature(Feature.L30, this.getLabel(3, 0)));
            // If the c-commanding node for this terminal node has been defined,
            // then fire the CCP and CC features
            if (CCommandingNode != null) {
                nodeFeatures.fire(
                    new Feature(
                        Feature.CCP,
                        CCommandingNode.lexicalHead.parent().label()));
                nodeFeatures.fire(
                    new Feature(
                        Feature.CC, CCommandingNode.lexicalHead.label()));
            }
            // add the local features of this node to the global feature vector
            subtreeFeatures = this.subtreeFeatures.add(nodeFeatures);
        }
    }

    public Node lexicalHead() {
        return lexicalHead;
    }

    public Node parent() {
        return this.parent;
    }

    /**
     * Recursively finds the lexical heads of each constituent in this subtree
     *
     * @param rules The head finder rules as described in Collins' thesis
     */
    public void percolateLexicalHeads(HeadFinderRules rules) {
        if (this.type == TERMINAL) {
            // The lexical head of a terminal is itself
            this.lexicalHead = this;
        } else if (this.type == POS) {
            // The lexical head of a POS tag is the lexical entry
            this.lexicalHead = this.children.getFirst();
        } else if (this.type == NONTERMINAL) {
            // Iterate through all the subtrees of this node and percolate the
            // lexical heads throughout its subtrees.
            for (Iterator<Node> it =
                    this.children.iterator(); it.hasNext(); ) {
                it.next().percolateLexicalHeads(rules);
            }

            // Fire the head finder rules depending on the node label
            if (this.value.equals(gen.create("NP"))
                    || this.value.equals(gen.create("NX"))
                    || this.value.toString().startsWith("NP")                     
                    || this.value.toString().startsWith("NX")) {
                this.lexicalHead = rules.NPConstituentRule.fire(this);
            } else if (this.value.equals(gen.create("ADJP"))
                       || this.value.toString().startsWith("ADJP")) {
                this.lexicalHead = rules.ADJPConstituentRule.fire(this);
            } else if (this.value.equals(gen.create("ADVP"))
                       || this.value.toString().startsWith("ADVP")) {
                this.lexicalHead = rules.ADVPConstituentRule.fire(this);
            } else if (this.value.equals(gen.create("CONJP"))
                       || this.value.toString().startsWith("CONJP")) {
                this.lexicalHead = rules.CONJPConstituentRule.fire(this);
            } else if (this.value.equals(gen.create("FRAG"))
                       || this.value.toString().startsWith("FRAG")) {
                this.lexicalHead = rules.FRAGConstituentRule.fire(this);
            } else if (this.value.equals(gen.create("INTJ"))
                       || this.value.toString().startsWith("INTJ")) {
                this.lexicalHead = rules.INTJConstituentRule.fire(this);
            } else if (this.value.equals(gen.create("LST"))
                       || this.value.toString().startsWith("LST")) {
                this.lexicalHead = rules.LSTConstituentRule.fire(this);
            } else if (this.value.equals(gen.create("NAC"))
                       || this.value.toString().startsWith("NAC")) {
                this.lexicalHead = rules.NACConstituentRule.fire(this);
            } else if (this.value.equals(gen.create("PP"))
                       || this.value.toString().startsWith("PP")) {
                this.lexicalHead = rules.PPConstituentRule.fire(this);
            } else if(this.value.equals(gen.create("PRN"))
                      || this.value.toString().startsWith("PRN")) {
                this.lexicalHead = rules.PRNConstituentRule.fire(this);
            } else if (this.value.equals(gen.create("PRT"))
                       || this.value.toString().startsWith("PRT")) {
                this.lexicalHead = rules.PRTConstituentRule.fire(this);
            } else if (this.value.equals(gen.create("QP"))
                       || this.value.toString().startsWith("QP")) {
                this.lexicalHead = rules.QPConstituentRule.fire(this);
            } else if (this.value.equals(gen.create("RRC"))
                       || this.value.toString().startsWith("RRC")) {
                this.lexicalHead = rules.RRCConstituentRule.fire(this);
            } else if (this.value.equals(gen.create("SBAR"))
                       || this.value.toString().startsWith("SBAR")) {
                this.lexicalHead = rules.SBARConstituentRule.fire(this);
            } else if (this.value.equals(gen.create("SBARQ"))
                       || this.value.toString().startsWith("SBARQ")) {
                this.lexicalHead = rules.SBARQConstituentRule.fire(this);
            } else if (this.value.equals(gen.create("S"))
                       || this.value.toString().startsWith("S")) {
                this.lexicalHead = rules.SConstituentRule.fire(this);
            } else if (this.value.equals(gen.create("SINV"))
                       || this.value.toString().startsWith("SINV")) {
                this.lexicalHead = rules.SINVConstituentRule.fire(this);
            } else if (this.value.equals(gen.create("SQ"))
                       || this.value.toString().startsWith("SQ")) {
                this.lexicalHead = rules.SQConstituentRule.fire(this);
            } else if (this.value.equals(gen.create("UCP"))
                       || this.value.toString().startsWith("UCP")) {
                this.lexicalHead = rules.UCPConstituentRule.fire(this);
            } else if (this.value.equals(gen.create("VP"))
                       || this.value.toString().startsWith("VP")) {
                this.lexicalHead = rules.VPConstituentRule.fire(this);
            } else if (this.value.equals(gen.create("WHADJP"))
                       || this.value.toString().startsWith("WHADJP")) {
                this.lexicalHead = rules.WHADJPConstituentRule.fire(this);
            } else if (this.value.equals(gen.create("WHADVP"))
                       || this.value.toString().startsWith("WHADVP")) {
                this.lexicalHead = rules.WHADVPConstituentRule.fire(this);
            } else if (this.value.equals(gen.create("WHNP"))
                       || this.value.toString().startsWith("WHNP")) {
                this.lexicalHead = rules.WHNPConstituentRule.fire(this);
            } else if (this.value.equals(gen.create("WHPP"))
                       || this.value.toString().startsWith("WHPP")) {
                this.lexicalHead = rules.WHPPConstituentRule.fire(this);
            } else if (this.value.toString().startsWith("X")) {
                this.lexicalHead = rules.VPConstituentRule.fire(this);
            } else {
                System.err.println("UNSEEN SYMBOL! " + this.value);
            }
        }
    }

    /**
     * Returns the score of the tree rooted at this node. The score is the sum
     * of each element in the dot product of the parameter vector and the global
     * feature vector for this tree.
     */
    public double score() {
        return (parameters.dotProduct(subtreeFeatures)).sum();
    }

    private String stringRep(int indent) {
        String ret = "";

        for (int i = 0; i < indent; i++) {
            ret += "  ";
        }
        if(this.type == NONTERMINAL || VERBOSE || STRUCTURE) {
            if(VERBOSE)
                ret += "( " + this.label() + ": " + this.subtreeFeatures + "\n";
            else if(STRUCTURE && this.lexicalHead != null)
                ret += "( " + this.label() + ": <" + this.lookAhead + "," + this.lookAheadPOS + "," + this.lexicalHead.label() + ">\n";
            else if(STRUCTURE && this.lexicalHead == null)
                ret += "( " + this.label() + ": <" + this.lookAhead + "," + this.lookAheadPOS + "," + this.lexicalHead + ">\n";
            else
                ret += "( " + this.label() + "\n";
            for (Iterator<Node> it = children.iterator(); it.hasNext(); ) {
                ret += it.next().stringRep(indent + 1);
            }

            for (int i = 0; i < indent; i++) {
                ret += "  ";
            }

            ret += ")\n";
        } else if(this.type == POS) {
                ret += "( " + this.label() + " " + this.children.getFirst().label() + ")\n";
        }
        return ret;
    }

    public String toString() {
        return this.stringRep(0);
    }

    // Added: 27 Feb 2007 (D.N. Mehay) -- for compatibility with Tree.java objects.
    public String toTreeString() {
        return this.treeStringRep(0);
    }
    
    private String treeStringRep(int indent) {
        String ret = "";

        for (int i = 0; i < indent; i++) {
            ret += "  ";
        } 
        
        String lab = this.label().toString();
        if(lab.trim().equals("S!")) lab=" ";
                
        if(this.type == NONTERMINAL || VERBOSE || STRUCTURE) {
            if(VERBOSE)
                ret += "(" + lab + ": " + this.subtreeFeatures;
            else if(STRUCTURE && this.lexicalHead != null)
                ret += "(" + lab + ": <" + this.lookAhead + "," + this.lookAheadPOS + "," + this.lexicalHead.label();
            else if(STRUCTURE && this.lexicalHead == null)
                ret += "(" + lab + ": <" + this.lookAhead + "," + this.lookAheadPOS + "," + this.lexicalHead;
            else
                ret += "(" + lab;
            String temp = "";
            for (Iterator<Node> it = children.iterator(); it.hasNext(); ) {
                temp = it.next().treeStringRep(1);
                if(temp.trim().equals("(STOP /S)")) temp = "";
                ret += temp;
            }

            for (int i = 0; i < indent; i++) {
                ret += "  ";
            }

            ret += ")\n";
        } else if(this.type == POS) {
                ret += "(" + this.label() + " " + this.children.getFirst().label() + ")";
        }
        return ret;
    }
    
    /**
     * @return the label of this node
     */
    public Symbol label() {
        return value;
    }
    
    /**
     * This is only to be used for development - to test the parser, to get some rudimentary
     * features from this parse tree
     */
    public String extractXMLGrammarRep() {
        if(this.type == POS) {
            return "<lex cat=\"" + this.value + "\" entry=\"" + this.children.getFirst().label() + "\"/>\n";
        }
        else if(this.type == NONTERMINAL) {
            String ret = "<rule lhs=\"" + this.value + "\">\n";
            String childrenXML = "";
            for(Iterator<Node> it = this.children.iterator(); it.hasNext();) {
                Node n = it.next();
                childrenXML += n.extractXMLGrammarRep();
                ret += "\t<child node=\"" + n.label() + "\"/>\n";
            }
            ret += "</rule>\n";
            return ret + childrenXML;
        }
        else {
            return "";
        }
    }

    /**
     * This method recursively copies the tree rooted at this node and returns
     * the copy
     */
    public Node copy() {
        // Create the node copy.
        Node ret = new Node(this);
        // set the generator, copy the local and global feature vectors, set the
        // parameters
        ret.gen = this.gen;
        ret.subtreeFeatures = this.subtreeFeatures.copy();
        ret.nodeFeatures = this.nodeFeatures.copy();
        ret.parameters = this.parameters;
        // If the type of node is a nonterminal, then copy each child and add them
        // as children to the return node.
        if(this.type == NONTERMINAL) {
            for(Iterator<Node> childIt = this.children.iterator(); childIt.hasNext();) {
                Node child = childIt.next().copy();
                ret.addChild(child);
            }
        // If the type of node is a POS, then create a Terminal Node subtree
        // and add it as a child to the return node.
        } else if(this.type == POS) {
            Node child = new Node(this.children.getFirst());
            child.subtreeFeatures = this.children.getFirst().subtreeFeatures.copy();
            child.nodeFeatures = this.children.getFirst().nodeFeatures.copy();
            ret.addChild(child);
        }
        return ret;
    }
    
    //~--- get methods --------------------------------------------------------

    /**
     * @return the reference to the C-Commanding node of this node in the tree.
     */
    public Node getCCommandingNode() {

        Node ret = this;
        while ((ret != null) && (ret.leftSibling == null)) {
            ret = ret.parent;
        }
        if (ret == null) {
            return null;
        }
        // Corrected by D.N. Mehay (given the above, the uncommented-out line
        // sets ret to the (left) c-commanding node).
        //Node parentHead = ret.parent.lexicalHead;
        //if (parentHead != null) {
        //    ret = parentHead;
        //} else {
            ret = ret.leftSibling;
        //}
        return ret;
    }

    public LinkedList<Node> getChildren() {
        return children;
    }

    /**
     * This is a tree walking method which returns a node parentIndex nodes upwards
     * and siblingIndex nodes leftwards.
     *
     * @param parentIndex the level of nodes upwards to "walk"
     * @param siblingIndex the level of nodes leftwards to "walk"
     */
    public Symbol getLabel(int parentIndex, int siblingIndex) {
        Node level = this;

        for (int i = 0; i < parentIndex; i++) {
            level = level.parent();

            if (level == null) {
                return null;
            }
        }

        Node tParentLevel = level.parent();

        if ((tParentLevel == null) && (siblingIndex != 0)) {
            return null;
        } else if ((tParentLevel == null) && (siblingIndex == 0)) {
            return level.label();
        }

        int thisIndex   = tParentLevel.children.indexOf(level);
        int targetIndex = thisIndex - siblingIndex;

        if (targetIndex < 0) {
            return null;
        }

        return ((Node) tParentLevel.children.get(targetIndex)).label();
    }

    /**
     * Determines if the tree rooted at this tree contains the tree rooted at <code>n</code>
     * as a prefix.
     */
    public boolean hasTreePrefix(Node n) {
        if (this.value.equals(n.value)) {
            boolean ret = true;
            for (int i = 0; i < n.getChildren().size(); i++) {
                ret &= this.children.get(i).hasTreePrefix(n.getChildren().get(i));
            }
            return ret;
        }
        return false;
    }

    /**
     * Returns the partial tree prefix of the tree
     *
     * @param end The length of the prefix. Cannot be greater than the length of
     * the sentence.
     */
    public Node getPrefix(int end) {
        // Create a copy of this node
        Node p = new Node(this.parent(), this.type, this.label(), this.lookAhead, this.lookAheadPOS, this.gen, this.parameters);
        // For each child of this node
        for(Iterator<Node> child = this.children.iterator(); child.hasNext();) {
            // Get the prefix of this node.
            Node c = child.next().getPrefix(end - p.getSentence().size());
            // add the prefix found as a child to p;
            p.addChild(c);
            // Needed because once it finds the sentence, it sets it in the node
            // and because we're adding children dynamically, we need to reset
            // the reference to the sentence.
            p.sentence = null;
            // break out of the loop if the length of the sentence spanned by p equals end
            if(p.getSentence().size() == end)
                break;
        }
        return p;
    }

    public Node getRightMostNode(int level) {
        Node ret = this;
        for(int i = 0; i < level; i++) {
            if(ret.type == TERMINAL)
                return null;
            ret = ret.children.getLast();
        }
        return ret;
    }
    
    public int compareTo(Object o) {
        Node other = (Node)o;
        if(this.score() == other.score()) {
            //System.out.println("(" + this.score() + ", " + other.score() + "):  " + "0");
            return 0;
        } else if(this.score() < other.score()) {
            //System.out.println("(" + this.score() + ", " + other.score() + "):  " + "-1");
            return -1;
        } else {
            //System.out.println("(" + this.score() + ", " + other.score() + "):  " + "1");
            return 1;
        }
    }
    
    /**
     * Returns the sentence which this tree spans.
     */
    public LinkedList<String> getSentence() {
        // If the reference ot the sentence is undefined
        if(this.sentence == null || this.sentence.size() == 0) {
            // recursively construct the sentence from the children of this node.
            LinkedList<String> ret = new LinkedList<String>();
            if(this.type == Node.TERMINAL) {
                ret.addLast(this.label().toString());
            } else {
                for(Iterator<Node> child = this.children.iterator(); child.hasNext();) {
                    ret.addAll(child.next().getSentence());
                }
            }
            this.sentence = ret;
        }
        return this.sentence;
    }
    
}


//~ Formatted by Jindent --- http://www.jindent.com
